// 最长递增子序列 [lower_bound待测试]
#include <bits/stdc++.h>
using namespace std;

int getLongestIncreasingSubquence(vector<int> vtNumber) {
  vector<int> dp(vtNumber.size() + 1);
  dp[1] = vtNumber[0];
  int nMaxLen = 1;
  for (int i = 1; i < vtNumber.size(); i++) {
    printf("now==%d\n", vtNumber[i]);
    if (vtNumber[i] > dp[nMaxLen]) {
      dp[++nMaxLen] = vtNumber[i];
    } else {
      auto it = lower_bound(dp.begin(), dp.end(), vtNumber[i]);
      int nPos = it - dp.begin();
      dp[nPos] = vtNumber[i];
    }
    for (auto n : dp) printf("%d,", n);
    printf("\n");
  }

  return nMaxLen;
}

int main() {
  printf("%d\n", getLongestIncreasingSubquence(
                     {2, 4, 1, 67, 45, 6, 9, 7, 8, 5, 4, 77}));
}
